package com.cjl.interview150.matrix;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class MatirxPractice {
    /**
     * 36. 有效的数独
     *
     * @param board
     * @return
     */
    public boolean isValidSudoku(char[][] board) {
        // 代表数字1-9在每一行每一列每一个小盒子中是否出现过
        int[][] row = new int[9][10];
        int[][] col = new int[9][10];
        int[][] box = new int[9][10];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                // 判断当前的数字是否在每一行每一列中出现过
                if (board[i][j] == '.') {
                    continue;
                }
                int curNum = board[i][j] - '0';
                int boxNum = j / 3 + (i / 3) * 3;
                if (row[i][curNum] == 1) return false;
                if (col[j][curNum] == 1) return false;
                if (box[boxNum][curNum] == 1) return false;
                // 没出现过，则记录
                row[i][curNum] = 1;
                col[j][curNum] = 1;
                box[boxNum][curNum] = 1;
            }
        }
        return true;
    }

    /**
     * 54. 螺旋矩阵
     *
     * @param matrix
     * @return
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        // 获取矩阵长宽
        int n = matrix.length;
        int m = matrix[0].length;
        // 定义上下左右边界
        int up = 0, down = n - 1, left = 0, right = m - 1;
        // 结果集
        ArrayList<Integer> res = new ArrayList<>();
        // 开始循环读取
        while (true) {
            // 从左到右读取上边界
            for (int i = left; i <= right; i++) {
                res.add(matrix[up][i]);
            }
            if (++up > down) {
                // 判断上边界是否越界
                break;
            }
            // 从上到下读取右边界
            for (int i = up; i <= down; i++) {
                res.add(matrix[i][right]);
            }
            if (--right < left) {
                break;
            }
            // 从右到左读取下边界
            for (int i = right; i >= left; i--) {
                res.add(matrix[down][i]);
            }
            if (--down < up) {
                break;
            }
            // 从下到上遍历左边界
            for (int i = down; i >= up; i--) {
                res.add(matrix[i][left]);
            }
            if (++left > right) {
                break;
            }
        }
        return res;
    }

    /**
     * 48. 旋转图像
     *
     * @param matrix
     */
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < (n + 1) / 2; j++) {
                // 开始四角转换
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = temp;
            }
        }
    }

    /**
     * 73. 矩阵置零
     *
     * @param matrix
     */
    public void setZeroes(int[][] matrix) {
        ArrayList<int[]> list = new ArrayList<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    list.add(new int[]{i, j});
                }
            }
        }
        for (int[] arr : list) {
            int row = arr[0];
            int col = arr[1];
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[i].length; j++) {
                    if (i == row || j == col) {
                        matrix[i][j] = 0;
                    }
                }
            }
        }
    }

    // 利用标记数组
    public void setZeroes2(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        // 定义标记数组
        boolean[] row = new boolean[n];
        boolean[] col = new boolean[m];
        // 标记0对应的行和列
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 0) {
                    // 将这一行和这一列标记为true
                    row[i] = col[j] = true;
                }
            }
        }
        // 根据标记数组对原数组进行操作
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

    /**
     * 289. 生命游戏
     * 游戏规则：
     * 1.如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
     * 2.如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
     * 3.如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
     * 4.如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
     * @param board
     */
    public void gameOfLife(int[][] board) {
        // 定义方向数组方便计算九宫格之内的细胞
        int[] direct = {0, 1, -1};
        // 获取矩阵行和列
        int rows = board.length;
        int cols = board[0].length;
        // 开始根据九宫格统计
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                // 对于每一个细胞统计其八个相邻位置里的活细胞数量
                int liveCell = 0;
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        // 如果是当前元素则直接跳过,不是则计算
                        if (!(direct[i] == 0 && direct[j] == 0)) {
                            int r = row + direct[i];
                            int c = col + direct[j];
                            if ((r >= 0 && r < rows) && (c >= 0 && c < cols) && (Math.abs(board[r][c]) == 1)) {
                                liveCell += 1;
                            }
                        }
                    }
                }
                // 根据当前细胞周围八个细胞的状态确定当前细胞是死是活
                if (board[row][col] == 1 && (liveCell < 2 || liveCell > 3)) {
                    // 之前是活的，现在死了
                    board[row][col] = -1;
                }
                if (board[row][col] == 0 && liveCell == 3) {
                    // 之前死了，现在复活
                    board[row][col] = 2;
                }
            }
        }
        // 重置细胞状态
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (board[row][col] > 0) {
                    board[row][col] = 1;
                } else {
                    board[row][col] = 0;
                }
            }
        }
    }


}
